import java.util.Arrays;
import java.util.Stack;

public class Sort {

    private static void display(int[] array) {
        for(int x : array) {
            System.out.print(x + " ");
        }
    }
    private static void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }


    // 插入排序(从大到小)
    public static void insertSort(int[] array){
        int[] tmpArray = Arrays.copyOf(array,array.length);
        if(tmpArray.length < 2) return;
        for(int i = 1; i < tmpArray.length; i++) {
            int tmp = tmpArray[i];
             // 从下标为 i-1的元素开始遍历， 比 array[i]大的元素都向后移动
            int j = i -1;
            for(; j >= 0; j--) {
                if(tmpArray[j] > tmp) {
                    tmpArray[j+1] = tmpArray[j];
                    // 此时array[j] < array[i]，此 j + 1下标 为 array[i] 在已排序元素中的位置
                }else {
                    tmpArray[j+1] = tmp;
                    break;
                }
            }
        }
        display(tmpArray);
    }


    public static void main(String[] args) {
        int[] array = {12,44,8,26,40,99,3,76,60,25,150,101,109};
        Sort2.radixSort(array);
        for (int x : array) {
            System.out.print(x + " ");
        }
    }




    // 希尔排序(从小到大)
    public static void shellSort(int[] array){
        int[] tmpArray = Arrays.copyOf(array,array.length);
        if(tmpArray.length < 2) return;
        int gap = tmpArray.length;
        while(gap > 1) {
            gap = gap / 2;
            shell(tmpArray, gap);
        }
        display(tmpArray);
    }
    private static void shell(int[] array, int gap) {
        for(int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for(; j >= 0; j -= gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }






    // 选择排序（从小到大）
    public static void selectSort(int[] array){
        int[] tmpArray = Arrays.copyOf(array,array.length);
        for(int i = 0; i < tmpArray.length - 1; i++) {
            int minIndex = i;
            for(int j = i + 1; j < tmpArray.length; j++) {
                if(tmpArray[j] < tmpArray[minIndex]) {
                    minIndex = j;
                }
            }
            swap(tmpArray, i, minIndex);
        }
        display(tmpArray);
    }
    //选择排序，分别定义左右两个”指针“，每次遍历分别找当前排序序列的最大值和最小值
    public static void selectSort2(int[] array) {
        int[] tmpArray = Arrays.copyOf(array,array.length);
        for(int i = 0; i < tmpArray.length / 2; i++) {
            int maxIndex = i;
            int minIndex = i;
            for(int j = i; j <= tmpArray.length - 1 - i; j++){
                if(tmpArray[j] > tmpArray[maxIndex]) maxIndex = j;
                if(tmpArray[j] < tmpArray[minIndex]) minIndex = j;
            }
            swap(tmpArray, minIndex, i);
            if(tmpArray[minIndex] > tmpArray[maxIndex]) {
                maxIndex = minIndex;
            }
            swap(tmpArray, maxIndex, tmpArray.length - 1 - i);
        }
        display(tmpArray);
    }







    // 堆排序
    public static void heapSort(int[] array){
        int[] tmpArray = Arrays.copyOf(array,array.length);
        createBigHeap(tmpArray);
        int end = tmpArray.length - 1;
        while(end > 0) {
            swap(tmpArray, 0, end);
            shiftDown(tmpArray, 0, end);
            end--;
        }
        display(tmpArray);
    }
    private static void createBigHeap(int[] array) {
        for(int parent = (array.length-2) / 2; parent >= 0; parent-- ) {
            shiftDown(array,parent, array.length);
        }
    }
    private static void shiftDown(int[] array, int root, int len) {
        int parent = root;
        int child = root * 2 + 1;
        while(child < len) {
            if(child + 1 < len && array[child] < array[child+1]) {
                child = child + 1;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }





    // 冒泡排序
    public static void bubbleSort(int[] array){
        int[] tmpArray = Arrays.copyOf(array,array.length);
        for (int i = 0; i < tmpArray.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < tmpArray.length - 1 - i; j++) {
                if(tmpArray[j] > tmpArray[j+1]) {
                    swap(tmpArray,j,j+1);
                    flag = true;
                }
            }
            if(!flag) break;
        }
        display(tmpArray);
    }









    // 快速排序（Hoare法）
    public static void quickSort(int[] array){
        int[] tmpArray = Arrays.copyOf(array,array.length);
        quick(tmpArray, 0, tmpArray.length - 1);
        display(tmpArray);
    }
    private static void quick(int[] tmpArray, int left, int right) {
        if(left >= right) return;    //代表此时 此时排序区间 只有一个元素 或者 排序区间不存在

        if(right - left + 1 <= 15) {
            //进行插入排序    优点：后面两层结点逐渐趋于有序，插入排序可以减少后面两层结点的递归次数
            insertSortRange(tmpArray, left, right);
            return;
        }

        //三数取中法：将左、右、中间三个元素中 值排在中间的元素， 与 left 位置的元素进行交换。
        //优点：在某些情况下，可以有效降低树的高度， 降低递归的复杂度
        int mid = (left + right) / 2;
        int minValueIndex = left;
        if(tmpArray[left] < tmpArray[right]) minValueIndex = right;
        if(tmpArray[minValueIndex] > tmpArray[mid]) minValueIndex = mid;
        swap(tmpArray, left, minValueIndex);

        int pivot = partition(tmpArray, left, right);
        quick(tmpArray,pivot + 1, right);
        quick(tmpArray,left, pivot - 1);

    }
    private static void insertSortRange(int[] array, int start, int end){
        for(int i = start + 1; i <= end; i++) {
            int tmp = array[i];
            int j = i -1;
            for(; j >= start; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    private static int partition(int[] tmpArray, int left, int right) {
        int tmp = tmpArray[left];
        int i = left;   // 记录基准值的下标
        while(left < right) {
            //必须先让 right 去寻找比tmp小的元素， 因为这样可以防止 一个大的元素 被错误地放到 数组的前面
            while(left < right && tmpArray[right] >= tmp) {
                right--;
            }
            while(left < right && tmpArray[left] <= tmp) {
                left++;
            }
            //此时 left 和 right 分别指向 大于和小于 tmp的元素
            swap(tmpArray,left,right);
        }

        swap(tmpArray, i, right);
        return right;
    }



    //快速排序（挖坑法）   优先使用
    public static void quickSort2(int[] array) {
        int[] tmpArray = Arrays.copyOf(array,array.length);
        quick2(tmpArray, 0, tmpArray.length - 1);
        display(tmpArray);
    }
    private static void quick2(int[] tmpArray, int left, int right) {
        if(left >= right) return;           //代表此时 此时排序区间 只有一个元素 或者 排序区间不存在

        if(right - left + 1 <= 15) {
            //进行插入排序    优点：后面两层结点逐渐趋于有序，插入排序可以减少后面两层结点的递归次数，且基本有序的数据用插入排序较快
            insertSortRange(tmpArray, left, right);
            return;
        }

        //三数取中法：将左、右、中间三个元素中 值排在中间的元素， 与 left 位置的元素进行交换。
        //优点：在某些情况下，可以有效降低树的高度， 降低递归的复杂度
        int mid = (left + right) / 2;
        int minValueIndex = left;
        if(tmpArray[left] < tmpArray[right]) minValueIndex = right;
        if(tmpArray[minValueIndex] > tmpArray[mid]) minValueIndex = mid;
        swap(tmpArray, left, minValueIndex);

        int pivot = partition2(tmpArray, left, right);
        quick2(tmpArray, left, pivot - 1);
        quick2(tmpArray, pivot + 1, right);
    }
    private static int partition2(int[] tmpArray, int left, int right) {
        int tmp = tmpArray[left];
        while(left < right) {
            while(left < right && tmpArray[right] >= tmp) {
                right--;
            }
            swap(tmpArray, left, right);
            while(left < right && tmpArray[left] <= tmp) {
                left++;
            }
            swap(tmpArray, left, right);
        }
        tmpArray[left] = tmp;
        return left;
    }


    //快速排序（非递归实现）
    public static void quickSortNor(int[] array) {
        int[] tmpArray = Arrays.copyOf(array, array.length);
        quickNor(tmpArray, 0, tmpArray.length - 1);
        display(tmpArray);
    }
    private static void quickNor(int[] array, int start, int end) {
        if(end - start + 1 < 2) return;     //代表数组中元素小于2个

        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        stack.push(end);
        while(!stack.empty()) {
            int right = stack.pop();
            int left = stack.pop();
            int pivot = partition2(array, left, right);
            if(pivot - 1 >left) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if((pivot + 1 < right)) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }







    //归并排序
    public static void mergeSort(int[] array) {
        int[] tmpArray = Arrays.copyOf(array, array.length);
        merge(tmpArray, 0 , tmpArray.length - 1);
        display(tmpArray);
    }
    private static void merge(int[] array, int left, int right) {
        if(left >= right) return;

        //分解小区间
        int mid = (left + right) / 2;
        merge(array, left, mid);
        merge(array, mid + 1, right);

        //合并小区间的有序数组
        int start1 = left;
        int start2 = mid + 1;
        int[] mergeArray = new int[right - left + 1];
        int k = 0;
        while(start1 <= mid && start2 <= right) {
            if(array[start1] <= array[start2]) {
                mergeArray[k++] = array[start1++];
            }else {
                mergeArray[k++] = array[start2++];
            }
        }
        while(start1 <= mid) {
            mergeArray[k++] = array[start1++];
        }
        while(start2 <= right) {
            mergeArray[k++] = array[start2++];
        }
        //将mergeArray数组中的元素 放回到 原来数组的合并区间内
        k = 0;
        while (left <= right) {
            array[left++] = mergeArray[k++];
        }
    }






    //计数排序
    public static void countSort(int[] array) {
        int[] tmpArray = Arrays.copyOf(array, array.length);
        int minVal = tmpArray[0];
        int maxVal = tmpArray[0];
        for (int i = 1; i < tmpArray.length; i++) {
            if(tmpArray[i] < minVal) minVal = tmpArray[i];
            if(tmpArray[i] > maxVal) maxVal = tmpArray[i];
        }
        int[] countArray = new int[maxVal - minVal + 1];
        count(tmpArray, countArray , minVal);
        //把排序好的数据写回到 tmpArray 数组中
        int k = 0;
        for (int i = 0; i < countArray.length; i++) {
            while(countArray[i] > 0) {
                tmpArray[k++] = i + minVal;
                countArray[i]--;
            }
        }

        display(tmpArray);
    }
    private static void count(int[] array, int[] countArray, int minVal) {
        for (int i = 0; i < array.length; i++) {
            countArray[array[i] - minVal]++;
        }
    }
}
